package 华为OD机试B卷复用题.进阶题;

import utils.MyUtil;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class HJ23_最小传输延时 {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner in = new Scanner(new File("src/main/java/华为OD机试B卷复用题/进阶题/input/23.txt"));
        MyUtil.START();
        Solution(in);
        MyUtil.END();
    }

    static int[][] edges;
    static int[] dist;
    // 经典迪杰斯特拉算法，下面可看作迪杰斯特拉算法代码模板
    static void Solution(Scanner in) {
        // 获取顶点数，边数
        int N = in.nextInt();
        int M = in.nextInt();
        // 初始化距离表，边表
        edges = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                edges[i][j] = Integer.MAX_VALUE;
            }
        }
        dist = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            dist[i] = Integer.MAX_VALUE;
        }
        // 获取所有边
        for (int i = 0; i < M; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            int c = in.nextInt();
            edges[a][b] = c;
        }
        // 获取起始顶点和终点
        int start = in.nextInt();
        int end = in.nextInt();
        // 处理，求解
        boolean[] isVisited = new boolean[N + 1];
        dist[start] = 0; // 把起始点距离设为0，注意不能设定其为已访问，因为后面还要靠它更新 dist 数组
        for (int i = 1; i < N; i++) { // 开始时已取 start，再取 N-1 次即可
            int min = Integer.MAX_VALUE;
            int minV = -1;
            for (int j = 1; j <= N; j++) {
                if (!isVisited[j] && dist[j] < min) {
                    min = dist[j];
                    minV = j;
                }
            }
            //            if (minV = -1) // 说明图不连通，可以在此做另外一些逻辑，与本题无关
            isVisited[minV] = true;
            for (int j = 1; j <= N; j++) {
                if (!isVisited[j] && dist[j] > dist[minV] + edges[minV][j]) {
                    dist[j] = dist[minV] + edges[minV][j];
                }
            }
        }
        System.out.println(dist[end]);
    }
}
